#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

struct ListNode
{
	int val;
	struct ListNode *next;
	ListNode(int x) : val(x), next(NULL)
	{
	}
};

struct TreeNode
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution
{
public:
	// 替换空格
	void replaceSpace(char *str, int length)
	{
		// 遍历字符串，计算空格数
		int count = 0;
		for (int i = 0; i < length; i++)
			if (str[i] == ' ')
				count++;

		// 替换后的字符总个数
		int newlen = length + 2 * count;
		// 定义双指针
		int old = length - 1;
		int newi = newlen - 1;

		// 遇到空格就替换，否则直接挪动数据到new指针位置
		while (old >= 0)
		{
			if (str[old] != ' ')
			{
				str[newi--] = str[old];
			}
			else
			{
				// 遇到空格，替换
				str[newi--] = '0';
				str[newi--] = '2';
				str[newi--] = '%';
			}
			old--;
		}
	}

	// 数组中出现次数超过一半的数字
	int MoreThanHalfNum_Solution(vector<int> &numbers)
	{
		int times = 1; // 计数
		int nums = numbers[0];

		for (int i = 1; i < numbers.size(); i++)
		{
			if (nums == numbers[i])
			{
				times++;
			}
			else
			{
				// 重新赋值
				if (times == 0)
				{
					nums = numbers[i];
					times = 1;
				}
				times--;
			}
		}
		// 到这里挑选出来了重复出现次数的最多的数字
		// 统计是否超过数组的一半
		int count = 0;
		for (int i = 0; i < numbers.size(); i++)
		{
			if (nums == numbers[i])
				count++;
		}

		return count > numbers.size() / 2 ? nums : 0;
	}

	// 从尾到头打印链表:通过递归的方式
	void printListFromTailToHeadDFS(vector<int> &v, ListNode *head)
	{
		if (head == nullptr)
			return;

		printListFromTailToHeadDFS(v, head->next);

		// 到这里，表示递归回，直接插入数据到v
		v.push_back(head->val);
	}

	vector<int> printListFromTailToHead(ListNode *head)
	{
		vector<int> v;
		printListFromTailToHeadDFS(v, head);

		return v;
	}

	// 重建二叉树
	TreeNode* reConstructBinaryTreeDFS(vector<int>& preOrder,int prestart, int preend, vector<int>& vinOrder, int vinstart, int vinend)
    {
        //递归结束条件
        if(prestart > preend || vinstart > vinend)
            return nullptr;

        //子树根节点,前序的首元素
        TreeNode* root = new TreeNode(preOrder[prestart]);

        for(auto i = vinstart; i <= vinend; i++) //找中序遍历的子树的根节点位置
        {
            if(preOrder[prestart] == vinOrder[i]) //找到了
            {
                //划分区间:左子树、右子树
                root->left = reConstructBinaryTreeDFS(preOrder, prestart + 1, prestart + (i - vinstart), vinOrder, vinstart, i - 1); //(i-vinstart)偏移量
                root->right = reConstructBinaryTreeDFS(preOrder, (i - vinstart) + prestart + 1, preend, vinOrder, i + 1, vinend);

                break;
            }
        }

        return root;
    }
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) 
    {
        if(preOrder.size() == 0 || vinOrder.size() == 0 || preOrder.size() != vinOrder.size()) 
            return nullptr;

        //利用递归的思想
        return reConstructBinaryTreeDFS(preOrder, 0, preOrder.size() - 1,  vinOrder, 0, vinOrder.size());
    }

	//斐波那契数列剪枝操作
private:
    unordered_map<int, int> um;
public:
    int fib(int n) 
    {
        if(n == 0 || n == 1) return n;

        int pre = 0;
        //优化：递归剪枝
        if(um.find(n - 1) == um.end())
        {
            //没有出现过,直接递归计算
            pre = fib(n - 1);
            //计算的值插入到um中，用于去重
            um.insert({n - 1, pre});
        }
        else
        {
            //重复出现
            pre = um[n - 1]; //直接赋值，不再计算
        }

        int ppre = 0;
        if(um.find(n - 2) == um.end())
        {
            ppre = fib(n - 2);
            um.insert({n - 2, ppre});
        }
        else
        { ppre = um[n - 2]; }


        return (pre + ppre) % 1000000007; //数值溢出
    }

	//矩形覆盖
	int rectCover(int number) 
    {
        if(number == 0 || number == 1) return number;
        //最后放置小矩形完全覆盖大矩形的方式有两种：
        //要么竖着放、要么横着放
        //对此，所有的覆盖方式，竖着+横着即可

        //创建dp表
        //初始化
        //填表
        int dpa = 1, dpv = 1; //横、竖
        int dp = 0;
        for(int i = 2; i <= number; i++)
        {
            dp = dpa + dpv;
            dpa = dpv;
            dpv = dp;
        }

        return dp;
    }

	//链表中倒数第k个节点
	ListNode* FindKthToTail(ListNode* pHead, int k) 
    {
        if(k < 0 || pHead == nullptr) return nullptr;

        //利用前后指针
        ListNode* cur = pHead;
        ListNode* prev = pHead;

        //先让前指针走k步
        while(k > 0 && cur) 
        {
            k--;
            cur = cur->next;
        }
        //前后指针同时走
        while(cur)
        {
            prev = prev->next;
            cur = cur->next;
        }

        return k > 0 ? nullptr : prev;
    }

};

//青蛙挑台阶
// int main() 
// {
//     //创建dp表
//     //初始化
//     //填表
//     int n = 0;
//     cin >> n;
//     int dp0 = 1, dp1 = 1, dp = 0;
//     //dp[i] = dp[i-1] + dp[i-2]
//     for(int i = 2; i <= n; i++)
//     {
//         dp = dp0 + dp1;
//         dp0 = dp1;
//         dp1 = dp;
//     }
//     cout << dp1;

//     return 0;
// }

//求二进制中1的个数
// int main() 
// {
//     long n = 0;
//     cin >> n;

//     int count = 0;

//     while(n)
//     {
//         n = n&(n - 1); //每次n&(n - 1)操作都会去除一个比特位为1的值
//         count++;
//     }

//     cout << count;

//     return 0;
// }

int main()
{
	return 0;
}